package leetcode.str;

import java.util.Arrays;

/**
 * 给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回  -1 。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：haystack = "sadbutsad", needle = "sad"
 * 输出：0
 * 解释："sad" 在下标 0 和 6 处匹配。
 * 第一个匹配项的下标是 0 ，所以返回 0 。
 * 示例 2：
 * <p>
 * 输入：haystack = "leetcode", needle = "leeto"
 * 输出：-1
 * 解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。
 * <p>
 * <p>
 * 提示：
 * <p>
 * 1 <= haystack.length, needle.length <= 104
 * haystack 和 needle 仅由小写英文字符组成
 */
public class LeetCode28_StrStr {

    public int strStr(String haystack, String needle) {
        int[] next = next(needle.toCharArray());
        char[] s = haystack.toCharArray();
        char[] s2 = needle.toCharArray();

        int i = 0;
        int j = 0;

//        while (i < s.length && j < next.length) {
//            if (s[i] == s2[j]) {
//                i++;
//                j++;
//            } else {
//                while (j > 0 && s[i] != s2[j]) {
//                    j = next[j - 1];
//                }
//                if (j == 0 && s[i] != s2[j]) {
//                    i++;
//                }
//            }
//        }

        while (i < s.length && j < next.length) {
            if (s[i] == s2[j]) {
                i++;
                j++;
            } else if (j > 0) {
                j = next[j - 1];
            } else {
                i++;
            }
        }

        if (j >= s2.length) {
            return i - j;
        }

        return -1;
    }

    private int[] next(char[] s) {
        int[] next = new int[s.length];
        int i = 1;
        int k = 0;
        next[0] = 0;

        for (; i < s.length; i++) {
            while (k > 0 && s[k] != s[i]) {
                k = next[k - 1];
            }
            if (s[k] == s[i]) {
                k++;
            }
//            else {
//                k = 0;
//            }
            next[i] = k;
        }
        return next;
    }

    public static void main(String[] args) {
        String needle = "a";
        char[] s2 = needle.toCharArray();
        LeetCode28_StrStr leetCode28_strStr = new LeetCode28_StrStr();
        System.out.println("new LeetCode28_StrStr().next(s2) = " + Arrays.toString(leetCode28_strStr.next(s2)));

    }
}
